The present invention generally relates to the field of sequential circuits and more particularly to the field of cascade decomposition of sequential circuits
Digital electronics sequential circuits have the property that the output depends not only on the present input but also on the past sequence of inputs. In effect, sequential circuits must be able to store something about the past history of inputs in order to produce the present output. Conventionally, a sequential circuit is synthesised as a forward path containing combinational logic and a feedback path that includes memory as shown for a Mealy sequential circuit in FIG. 1. In such an implementation the cycle time is measured from input to updating the memory.
Sequential circuits have a wide variety of applications such as code converters, sequence detectors, controllers, etc. and their speed of operation i.e. their cycle time can be a limitation in electronic equipment.
Thus, work has been carried out in an attempt to improve the speed of operation of sequential circuits.
It is known that the implementation of the sequential circuit as a set of interacting sequential circuits functioning concurrently i.e. in parallel is desirable primarily because of the resulting improvements in performance.
One such method is a decomposition approach based on the Algebraic Structure Theory disclosed in a book by J. HartManis and R. E. Stearns (xe2x80x9cAlgebraic Structure Theory of Sequential Machinesxe2x80x9d, Prentis Hall, Englewood Cliffs, 1996). This work has been further analysed in a paper by M. Geiger and T. Mxc3xclle-Wipperfxc3xcrth (xe2x80x9cFSM Decomposition revisited: Algebraic Structure Theory applied to MCNC Benchmark FSMSxe2x80x9d, 28th ACM/IEEE Design Automation Conference, 1991, ACMO-89791-395-7/91/0006/0182, pages 182 to 185). In this approach a sequential circuit is decomposed into a cascade of component sequential circuits. In such a configuration all of the component sequential circuits function concurrently. It has been shown that such an approach can result in reduced cycle time and reduced circuit components and/or a reduced circuit area. However, such an approach relies on determining partitions and it is known that partitions are scarce. Consequentially, such methods rarely yield a decomposition and if they do it is typically only into two or three smaller machines.
It is known in the Algebra Structure Theory of K. Krohn and J. L. Rhodes (xe2x80x9cAlgebraic Theory of Machines, I Prane Decomposition Theorem for Finite Semi-Groups and Machinesxe2x80x9d Trans. Amer. Math. Soc. Vol. 116 (1965) pages 450 to 464) and from the later work by H. P. Zeiger (xe2x80x9cCascade Synthesis of Finite State Machinesxe2x80x9d Information and Control, 1967, pages 419 to 433) that the state transition graph of a sequential circuit gives rise to an algebraic structure known as a semi-group and that a semi-group can be decomposed into component semi-groups. Moreover, each decomposition of the semi-group results in a decomposition of the sequential circuit into a cascade of component sequential circuits as shown in FIG. 2 such that each machine is a permutation reset machine.
The problem of the approach of Zeiger is that his method requires the calculation of the semi-group of the sequential circuit and this can be very large. Thus the method is not generally implementable. Since the technique calculates functions for all possible sequences of inputs this can give rise to pp functions where p is the number of states in the given circuit. If the elementary functions are not fully defined the number of functions can be larger than pp. Further, as can be seen in FIG. 2, the input to the pth circuit is the output of all the previous p-1 circuits. Clearly even for p the amount of wiring between the circuits becomes considerable and the calculations of the component machines becomes very difficult. FIG. 2 is only a schematic drawing and only shows one wire output for each circuit. In fact the number of wires is at least as large as the number of bits required to encode the states of the machine.
It is therefore an object of the present invention to provide a sequential circuit design and method in which the disadvantages of the prior art methods are overcome and a sequential circuit of reduced cycle time is produced.
In accordance with one aspect of the present invention there is provided a method and apparatus for determining the decomposition of a sequential circuit which does not require the semi-group to be calculated. From the state transition graph of the sequential circuit, a dynamic data structure is generated which represents all the information required to determine the component sequential circuits.
In accordance with another aspect of the present invention the above mentioned data structure is utilised so as to optimise the wiring so that the resulting decomposition only requires a single connection between each component sequential circuit.
In accordance with a further aspect of the present invention there is provided a method and apparatus for generating finite state graphs for designing a cascade decomposed sequential circuit from an input finite state graph for a sequential circuit, wherein functions are determined defining all transitions from the current state to a next state of the logic circuit caused by an input to the logic circuit, sets of states which include the possible state of the logic circuit are determined using the functions, the levels are assigned to the sets such that each level corresponds to one of a cascaded plurality of circuit units, each circuit unit is defined to have a plurality of the states, where each state comprises a set of states of the sequential circuit, the sets of states are assigned to the plurality of cascaded circuit units on the basis of the assigned levels such that at least two states of the circuit unit are subsets of a set of states of an immediately preceding circuit unit in the cascade, where the subsets are a cover of the set, and at least one circuit unit has a state which is a set of states of an immediately preceding circuit unit in the cascade, and next sets of states for the circuit unit are determined using the functions and the states of a proceeding circuit unit in the cascade.
In this aspect of the present invention an input can comprise any number of bits which are input within an instance in time. Where there are no transitions between states for an input the functions need not be defined.
The term xe2x80x9clogicxe2x80x9d is used to describe the usual circuit components used to build sequential circuits and includes logic gates and memory devices for example.
Thus, in this aspect of the present invention, extra states are added to at least one circuit unit and instead of using wires to pass states of one circuit unit to another circuit unit so that intermediate circuit units are by passed, logic is used within the intermediate circuit units to store and thereby pass on the states of the proceeding circuit units. In this way the wiring required is reduced and instead extra logic may be added if necessary into the intermediate circuit units thereby increasing the number of states of those intermediate circuit units.
Another aspect of the present invention provides a method and apparatus wherein the functions defining all the transitions from a current state to a next state of the logic circuit caused by a single input to the logic circuit are determined, sets of states which comprise possible states of the logic circuit are determined using the functions thereby ensuring that the sequences of actions which cannot possibly take place are not defined, and levels are assigned to the sets, where each level corresponds to one of the cascaded plurality of the said units, the sets of states are assigned to the cascaded circuit units on the basis of the assigned levels, information on the states of the preceding circuit units are passed along the cascade, and determining next states for the sequential circuit components using said functions and the states of preceding sequential circuit components in the cascade.
In accordance with this embodiment since sets of states are determined using the functions which are only defined for a single input to the sequential circuit and these are applied sequentially to determined sets of states, only sets of states are defined which contain a state in which the circuit can exists This technique no longer requires the calculation of the possible nn functions that may require calculations of possible 2n. Further, it is evident from such a technique that it is not always necessary to pass on the states of a circuit unit onto all subsequent circuit units if the state is processed in the next circuit unit and thus wiring can be reduced.
In accordance with another aspect of the present invention there is provided a sequential logic circuit for receiving an input and for generating an output wherein the logic circuit comprises at least three interacting sequential circuit units each functioning concurrently, each sequential circuit unit having an input means for receiving the input, at least one of the sequential circuits having a second input means for receiving one further input only an immediately preceding sequential circuit unit in the sequence, and the last of the sequential circuit units in the sequence having an output means for generating the output.
In accordance with a further aspect of the present invention there is provided a sequential logic circuit for receiving an input and for generating an output, the logic circuit comprising a plurality of interacting sequential circuit units which function concurrently, each said sequential circuit unit having input means for receiving the input, at least one of said sequential circuits having second input means for receiving only one further input from only an immediately preceding sequential circuit unit in the sequence, the last of said sequential circuit units, in the sequence having output means for generating the output, and at least one of the sequential circuit units is not a permutation reset machine.
A further advantage of this aspect of the present invention is that each of the circuit units is not limited to being a permutation reset circuit thus giving the circuit wider applications.
In an embodiment of the present invention the sequential circuit can be fully decomposed such that the only wiring between the circuit units comprises wires connecting immediately adjacent circuit units such that states of the circuit units which are not conventionally used as an input to an adjacent circuit unit are input into the adjacent circuit unit and simply passed therethrough until they reach a circuit unit where they are required as an input.
In such an embodiment where the number of states to be passed on becomes large, in order to reduce the amount of logic required in each circuit unit, it is preferable to feeding on the states of a circuit unit having such a large number of states using the wiring technique. This is an optimisation technique requiring a decision as to whether it is preferable to use a large amount of logic or to increase the amount of wiring between the circuit units. The use of the feed forward wiring is possible at any stage using prior art methods but in most cases desirable when sets of states are identified which can transit between each other in the manner of a closed loop. Such sets are defined as equivalent and are represented by a single one of the sets.
Another form of optimisation which can be used in an embodiment of the present invention is the merging of circuit units i.e. the reduction of the decomposition of the sequential circuit. This can either be achieved by stopping the decomposition of the sequential circuit i.e. by not determining the states of each sequential circuit unit, or by combining the states of adjacent circuit units after they have been determined. For example, in order to reduce processing it may be desirable to identify when the number of states of a circuit unit reach a threshold and to attempt to merge the circuit units thereafter in the sequence in order to reduce the amount of logic used in building the complete sequential circuit. Alternatively, once the fully decomposed sequential circuit has been designed, the performance of each of the circuit units can be determined and merging of circuit units can take place thereafter in dependence upon the performance of each of the circuit units. For example, if one of the circuit units operates particularly slowly, and therefore represents a bottleneck in the simultaneous pipeline processing, circuit units upstream or downstream of the bottleneck in the sequence can be merged thereby reducing the amount of logic without affecting the overall performance of the sequential circuit.
In accordance with a further aspect of the present invention there is provided a method of apparatus of generating finite state data for designing a cascade decompose sequential circuit for the finite state data defining current states, next states, input states and output states for a sequential circuit, the method comprising:
determining functions defining transitions from a current state to a next state of the sequential circuit caused by any of a number of possible input states to the sequential circuit;
determining sets of states which include the possible states of the sequential circuit using said functions;
determining a plurality of equivalence classes of sets of states, each said equivalence class being determined to comprise one said set and any further said sets to which said one set can transit by application of said functions and from which said one set can be transmitted to by application of said functions;
assigning a level to the sets of each said equivalence class, sets of each equivalence class being assigned the same level, each level corresponding to one of a cascaded plurality of sequential circuit components;
assigning said sets of states as states of said cascaded plurality of sequential circuit components on the basis of the assigned levels;
identifying any of the equivalence classes comprising only one said set;
for any said sequential circuit component corresponding to a said equivalence class identified by the identifying step, using the states of the sequential circuit component as inputs for only the next sequential circuit component in the cascade; and
determining next states for the sequential circuit components using said functions and the states of at least one preceding sequential circuit component in the cascade as an input.
In accordance with this aspect of the present invention if an equivalence class only comprises one set, it is necessary for states of the circuit component to be passed on only to the next circuit component. In this way the amount of wiring is reduced. Thus the present inventors have realised that, in contrast to the technique of Krohn and Rhodes, it is not necessary in all circumstances to always pass on the states of every machine in a cascade to all the subsequent machine as an input. For any machine which has an equivalence class comprising only one member set, the wiring should simply only be to the next machine in the sequence. Alternatively, by identifying the points at which the wiring may be necessary, a designing can be given the option of either to use the wiring to pass on the states of the machine to each subsequent machine in the sequence, or to assign the states of the machine to the states of one or more subsequent machines whereby the states can be passed through one or more intermediate machines to reach a machine having those states.
In an embodiment of the present invention the finite state graph produced for the decomposed sequential circuit is in symbolic form and must subsequentially be state assigned to generate the finite state data in binary form used in the design of the logic for the sequential circuit. The state assignment for each of the circuit units can either be carried out as the states for each circuit unit are sequentially determined, or at the end when the symbolic states for all the circuit units have been determined. In this latter method the state assignment of each circuit unit can take place sequentially since the input to a subsequent circuit unit is defined as a binary state of a proceeding circuit unit.
In the embodiment of the present invention the levels or heights which are assigned to the states are dependent upon the order of generation and set containment e.g. the size of the sets and their order of generation during the sequential generation of the sets using the functions.
One aspect of the present invention also provides a method of manufacturing a decomposed sequential circuit wherein the finite state graphs are used for determining the circuit logic and the sequential circuit is manufactured in accordance with the determined logic design.
Since the present invention can be implemented on a computer, the present invention can also be provided as a storage medium containing instructions for controlling a processing apparatus to carry out the generation of the finite state graphs for designing the cascaded decomposed sequential circuit.
Techniques of optimal state assignment in order to determine the binary encoding of states are well known in the art e.g. the method described by J. R. Story, H. J. Harrison, E. A. Reinhard in a paper entitled xe2x80x9cOptimum state assignment for Syndromes Sequential Circuitsxe2x80x9d (IEEE Transactions Vol. C-21, December 1972, pages 1365 to 1373) and will thus not be described in detail.